/**
 * 
 */
package model.container.edges;

import java.util.HashMap;
import java.util.NoSuchElementException;

import model.Edge;

public class TasBinaireMinimal extends Edges {
	/**
	 * We will be using a HashMap to store the Item.
	 * A node has a index, and a value (Edge).
	 * A node at the i index, has two sons : 2i : 2i+1
	 */
	private HashMap<Integer, Edge> items = new HashMap<Integer, Edge>();

	@Override
	public String toString() {
		return items.toString();
	}
	
	@Override
	public Edge getMinimal() {
		if(isEmpty())
			throw new NoSuchElementException("Heap is empty");

		//System.out.println(getClass()+" [+] Getting minimal");
		Edge e = items.get(1);
		//System.out.println(getClass()+" [+] Got (1) : "+e);
		items.put(1, items.get(items.size()));
		items.remove(items.size());
		moveDown(1);
		return e;
	}

	@Override
	public void addItem(Edge e) {
		// let's add this Item at the end
		addItemAt(items.size()+1, e);
	}

	@Override
	public boolean isEmpty() {
		return items.isEmpty();
	}
	
	@Override
	public int getSize() {
		return items.size();
	}

	/**
	 * Add an Item at specified index
	 * @param idx the index
	 * @param e the Item to add
	 */
	private void addItemAt(int idx, Edge e) {
		//System.out.println(this.getClass()+" [+] Adding item at "+idx+" : "+e);
		items.put(idx, e);
		moveUp(idx);
	}

	/**
	 * Get the parent index
	 * @param idx
	 * @return the parent index
	 */
	private static int getParentIdx(int idx) {
		return (idx-(idx%2))/2;
	}

	/**
	 * Switch the positions of 2 items
	 * @param idx1 the index of the first Item
	 * @param idx2 the index of the second Item
	 */
	private void switchItem(int idx1, int idx2) {
		Edge e = items.get(idx1);
		items.put(idx1, items.get(idx2));
		items.put(idx2, e);
	}
	
	/**
	 * Recursive method, will move a Item upward.
	 * Stop at the root or at the right spot.
	 * @param idx the index of the Item to move
	 */
	private void moveUp(int idx) {
		// we stop if we are at the root OR if the parent cost is lower than ours 
		if(idx == 1 || items.get(idx).getCost() >= items.get(getParentIdx(idx)).getCost())
			return;

		//System.out.println(this.getClass()+" [+] Moving up "+items.get(idx)+" : "+idx+" => "+getParentIdx(idx));
		switchItem(idx, getParentIdx(idx));
		moveUp(getParentIdx(idx));
	}
	
	private void moveDown(int idx) {
		int c1 = Integer.MAX_VALUE;
		int c2 = Integer.MAX_VALUE;
		int nIdx;
		if(2*idx <= getSize())
			c1 = items.get(2*idx).getCost();
		if(2*idx+1 <= getSize())
			c2 = items.get(2*idx+1).getCost();

		// we stop if we are at the bottom OR if both children cost are higher than ours
		if( c1 > items.get(idx).getCost() && c2 > items.get(idx).getCost() )
			return;
		
		nIdx = c1 < c2 ? 2*idx : 2*idx+1;
		//System.out.println(this.getClass()+" [+] Moving down "+items.get(idx)+" : "+idx+" => "+nIdx);
		switchItem(idx, nIdx);
		moveDown(nIdx);
	}
}